package com.java.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中缀表达式 7*(2*2/(5+1)-50+3-4)
 * 中缀表达式转换成后缀表达式
 * 完成逆波兰计算器
 * @author 19252
 * @date 2020/7/11
 */
public class ReversePolishDemo2 {

    public static void main(String[] args) {
        // 获得一个表达式，直接对字符串操作比较麻烦，将它转换为一个集合方便操作
        String expression = "1+((2+3)*4)-5";
        ReversePolishDemo2 demo2 = new ReversePolishDemo2();
        List<String> infix = demo2.expressionToArrayList(expression);
        System.out.println("infix = " + infix);
        List<String> suffix = demo2.infixToSuffix(infix);
        System.out.println("suffix = " + suffix);
        System.out.println(demo2.calculate(suffix));
    }

    /**
     * 将字符串转换为 一个list的集合
     * @param expression 输入的表达式
     * @return 返回表达式拆分成的String集合
     */
    public List<String> expressionToArrayList(String expression){
        List<String> array = new ArrayList<>();
        StringBuilder temp = new StringBuilder();
        char c;
        // 状态标记，判断 temp中是否有数据
        boolean flag2 = false;
        // 开始遍历
        for (int i = 0; i < expression.length(); i++) {
            // 获得字符串中的每一个字符
            c  =expression.charAt(i);
            // c < 48 || c > 57 c 为非数字
            boolean flag = (c < 48 || c > 57);
            if (flag){
                // flag2 == true 则证明 temp中有数据
                if (flag2){
                    array.add(String.valueOf(temp));
                    // 清空上一次的数字
                    temp.delete(0, temp.length());
                }
                array.add(String.valueOf(c));
                flag2 = false;
            }else {
                // 字符串拼接
                temp.append(c);
                // 最后一个数，置入array中
                if (i == expression.length() -1){
                    array.add(String.valueOf(temp));
                }
                flag2 = true;
            }
        }
        return array;
    }

    /**
     * 将一个中缀表达式转换成后缀表达式
     * @param list 包含了中缀表达式的list
     * @return 返回包含了后缀表达式的list
     */
    public List<String> infixToSuffix(List<String> list){
        // 定义一个符号栈
        Stack<String> s1 = new Stack<>();
        // 原本要定义一个存储中间结果的栈 s2，但在整个转换过程中，s2没有pop操作，
        // 而且在最后输出结果的时候是以 list逆序输出，所以在这里直接以list来操作
        // 存储中间结果的 s2
        ArrayList<String> s2 = new ArrayList<>();

        // 开始遍历 list
        String item;
        for (String s : list) {
            item = s;
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if ("(".equals(item)) {
                s1.push(item);
            } else if (")".equals(item)) {
                // 如果是 ')'，则依次弹出s1栈顶的运算符，
                // 并压入s2，直到遇到左括号未知，此时将一对括号丢弃
                while (!"(".equals(s1.peek())) {
                    s2.add(s1.pop());
                }
                // 将 '('出栈，这里就是在消除 ()
                s1.pop();
            } else {
                // 当item的优先级的小于等于s1栈定的运算符，将s1栈顶的运算符弹出并压入到s2中，与s1中的新的栈顶运算符相比较
                // 当进行上述操作后，s1为空或者 栈顶为 "(", 直接将item放入s1
                while (s1.size() != 0 && operatorPriority(s1.peek()) >= operatorPriority(item)) {
                    s2.add(s1.pop());
                }
                // 还需要将item压入栈
                s1.push(item);
            }
        }
        // 将s1 中的剩余的运算符依次弹出并加入 s2
        while (s1.size() != 0){
            s2.add(s1.pop());
        }
        // 因为List本身就是有序的，则得到的s2按顺序输出就是我们需要的后缀表达式
        return s2;
    }

    /**
     * 运算符的优先级
     * @return 返回运算符的优先级
     */
    public static int operatorPriority(String operator){
        int priority = 0;
        switch (operator){
            case "+":
            case "-":
                priority = 1;
                break;
            case "*":
            case "/":
                priority = 2;
                break;
            default:
                System.out.println("不存在该运算符！");
                break;
        }
        return priority;
    }

    /**
     * 对表达式进行计算
     * @param list 传入的表达式
     * @return 计算结果
     */
    public int calculate(List<String> list){
        Stack<String> stack = new Stack<>();
        int val1;
        int val2;
        int result = 0;
        for (String sub : list) {
            // sub 是数字的话，就入栈
            if (sub.matches("\\d+")) {
                stack.push(sub);
            } else {
                val1 = Integer.parseInt(stack.pop());
                val2 = Integer.parseInt(stack.pop());
                switch (sub) {
                    case "+":
                        result = val1 + val2;
                        break;
                    case "-":
                        result = val2 - val1;
                        break;
                    case "*":
                        result = val1 * val2;
                        break;
                    case "/":
                        result = val2 / val1;
                        break;
                    default:
                        break;
                }
                stack.push(String.valueOf(result));
            }
        }
        // 输出栈中最后的数据，这就是计算结果
        return Integer.parseInt(stack.pop());
    }
}
